package bintree.leetcode;

public class Num668乘法表中第k小的数 {
    public int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m*n;//9
        while (left<right){
            int mid = left+(right-left)/2;//5//3//2//2
            if (count(m,n,mid)>=k){
                right=mid;//5//3
            }else {
                left=mid+1;//2//3
            }
        }
        return left;
    }

    private int count(int m, int n, int k) {
        int ret = 0;
        for (int i = 1; i <=m; i++) {
            ret+=Math.min(k/i,n);
        }
        return ret;//6//5//3//3
    }
}
